package com.ai.zuochengyun.phase01.class05;

public class Code03_NumberOfIslands {

    public static void main(String[] args) {
        int row = 1000;
        int col = 1000;
        char[][] board1 = null;
        char[][] board2 = null;

        board1 = generateRandomMatrix(row, col);
        board2 = copy(board1);

        long start = System.currentTimeMillis(), end = 0;
        System.out.println("使用感染方法的运行结果："+numIslands(board1));
        end = System.currentTimeMillis();
        System.out.println("使用感染方法的运行耗时："+(end-start));

        start = System.currentTimeMillis();
        System.out.println("使用并查集（数组实现）方法的运行结果："+numIslands2(board2));
        end = System.currentTimeMillis();
        System.out.println("使用并查集（数组实现）方法的运行耗时："+(end-start));
    }

    private static char[][] generateRandomMatrix(int row, int col) {
        char[][] board = new char[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                board[i][j] = Math.random() < 0.5 ? '1' : '0';
            }
        }
        return board;
    }

    private static char[][] copy(char[][] board) {
        int row = board.length;
        int col = board[0].length;
        char[][] ans = new char[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                ans[i][j] = board[i][j];
            }
        }
        return ans;
    }

    /**
     * 使用上下左右遍历的方式去获取连接岛
     *
     * @param board
     * @return
     */
    public static int numIslands(char[][] board) {
        int islands = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '1') {
                    islands++;
                    infect(board, i, j);
                }
            }
        }
        // 数据还原
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '2') {
                    board[i][j] = 1;
                }
            }
        }
        return islands;
    }

    /**
     * 感染方法
     *
     * @param board
     * @param i
     * @param j
     */
    private static void infect(char[][] board, int i, int j) {
        // 下标越界了，就直接返回
        if (i < 0 || i >= board.length || j < 0 || j >= board.length) {
            return;
        }
        // 如果当前来的格子的值不是1，也返回
        if (board[i][j] != '1') {
            return;
        }
        // 当前格子标记为2，表明已经查看过了，下次不用再查看
        board[i][j] = '2';
        // 从当前格子的上下左右方向去查看，并感染
        infect(board, i - 1, j);
        infect(board, i + 1, j);
        infect(board, i, j - 1);
        infect(board, i, j + 1);
    }

    public static int numIslands2(char[][] board) {
        int row = board.length;
        int col = board[0].length;

        UnionFind2 uf = new UnionFind2(board);
        // 第一个for循环，来遍历第一行的数据，因为这一行上面的没有元素
        for (int i = 1; i < col; i++) {
            if (board[0][i - 1] == '1' && board[0][i] == '1') {
                uf.union(0, i - 1, 0, i);
            }
        }
        // 第二个for循环，来遍历第一列的数据，因为这一列左面的没有元素
        for (int i = 1; i < row; i++) {
            if (board[i - 1][0] == '1' && board[i][0] == '1') {
                uf.union(i - 1, 0, i, 0);
            }
        }
        // 第三个for循环，来获取既有上一行也有左列的数据
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (board[i][j] == '1') {
                    // 当前位置的上边为1吗，是就合并
                    if (board[i - 1][j] == '1') {
                        uf.union(i, j, i - 1, j);
                    }

                    // 当前位置的左边为1吗，是就合并
                    if (board[i][j - 1] == '1') {
                        uf.union(i, j, i, j - 1);
                    }
                }
            }
        }
        return uf.sets;
    }

    public static class UnionFind2 {
        private final int[] parent;

        private final int[] size;

        private final int[] help;

        private final int colSize;

        private int sets;

        /**
         * 将board二维数组中的所有元素，都转换成一个一维数组存储
         *
         * @param board
         */
        public UnionFind2(char[][] board) {
            colSize = board[0].length;
            sets = 0;
            int row = board.length;

            // 将二位数组转换成一个一维数组
            int len = row * colSize;
            parent = new int[len];
            size = new int[len];
            help = new int[len];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < colSize; j++) {
                    if (board[i][j] == '1') {
                        int loc = index(i, j);
                        // loc位置的parent就位于loc位置
                        parent[loc] = loc;
                        size[loc] = 1;
                        sets++;
                    }
                }
            }
        }

        /**
         * 通过所在行和列换算一个下标
         *
         * @param r
         * @param c
         * @return
         */
        private int index(int r, int c) {
            return r * colSize + c;
        }

        // 找到当前位置对应的代表节点位置，并将这个链路上的节点扁平化
        private int find(int loc) {
            int helpIndex = 0;
            while (loc != parent[loc]) {
                help[helpIndex++] = loc;
                loc = parent[loc];
            }

            // 扁平化
            for (helpIndex--; helpIndex >= 0; helpIndex--) {
                parent[help[helpIndex]] = loc;
            }
            return loc;
        }

        /**
         * 将（r1,c1）位置的节点和（r2,c2）位置的节点进行union操作
         *
         * @param r1
         * @param c1
         * @param r2
         * @param c2
         */
        private void union(int r1, int c1, int r2, int c2) {
            int head1 = find(index(r1, c1));
            int head2 = find(index(r2, c2));
            if (head1 != head2) {
                // 小数量的加入到大数量的，小挂大，降低层级
                // 合并后，size需要接纳融入的数量，并且要将小头挂大头
                if (size[head1] >= size[head2]) {
                    size[head1] += size[head2];
                    parent[head2] = head1;
                } else {
                    size[head2] += size[head1];
                    parent[head1] = head2;
                }
                // 有一个集合已经被合并了，所以集合数量减一
                sets--;
            }
        }

        private int sets() {
            return sets;
        }
    }


}
